﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0070_NumIslands : IAlgorithm
    {
        // 200. 岛屿数量

        // 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
        // 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
        // 此外，你可以假设该网格的四条边均被水包围。

        // 提示：
        //  m == grid.length
        //  n == grid[i].length
        //  1 <= m, n <= 300
        //  grid[i][j] 的值为 '0' 或 '1'

        public void Test()
        {
            // 算法参数定义
            var grid = new char[][] {
                new char[]{ '1','1','1','1','0' },
                new char[]{ '1','1','0','1','0' },
                new char[]{ '1','1','0','0','0' },
                new char[]{ '0','0','1','0','1' },
            };
            // 算法执行与打印
            Console.WriteLine(NumIslands(grid));
        }

        // 算法
        public int NumIslands(char[][] grid)
        {
            var direction = new int[][] {
                new int[] { 0, -1 },
                new int[] { 1, 0 },
                new int[] { 0, 1 },
                new int[] { -1, 0 },
            };
            int m = grid.Length, n = grid[0].Length, count = 0;
            var stack = new Stack<int[]>();
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] == '0')
                        continue;
                    count++;
                    stack.Push(new int[] { i, j });
                    while (stack.Count > 0)
                    {
                        var tempPoint = stack.Pop();
                        grid[tempPoint[0]][tempPoint[1]] = '0';
                        for (int k = 0; k < 4; k++)
                        {
                            var newX = tempPoint[0] + direction[k][0];
                            var newY = tempPoint[1] + direction[k][1];
                            if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == '1')
                                stack.Push(new int[] { newX, newY });
                        }
                    }
                }
            }
            return count;
        }

        public int NumIslands1(char[][] grid)
        {
            if (grid == null || grid.Length == 0)
                return 0;
            int nr = grid.Length;
            int nc = grid[0].Length;
            int num_islands = 0;
            for (int r = 0; r < nr; ++r)
                for (int c = 0; c < nc; ++c)
                    if (grid[r][c] == '1')
                    {
                        ++num_islands;
                        dfs(grid, r, c);
                    }
            return num_islands;
        }
        void dfs(char[][] grid, int r, int c)
        {
            int nr = grid.Length;
            int nc = grid[0].Length;
            if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0')
                return;
            grid[r][c] = '0';
            dfs(grid, r - 1, c);
            dfs(grid, r + 1, c);
            dfs(grid, r, c - 1);
            dfs(grid, r, c + 1);
        }
    }
}
